(talk) authenticated data structures for stateless validation

2022-08-11 · 2 min read

why #

Merkle Trees can't do some things efficiently
- Succinctness
- Proof and digest updates
- Proof aggregation
These are needed in new applications
- Transparency logs (e.g., x509 Certificate Transparency)
- Stateless validation (e.g., sharded eth, eth light clients)
These things are possible with new techniques
- Polynomial commitments
- Hidden-order groups (e.g. RSA)

CA gets compromised and issues bad cert for high-value domain like google.com.
Instead of preventing the problem (basically impossible), just detect bad CAs and remove them from browser/OS trust roots after the fact (when they're detected).
Client gets an extra CT inclusion proof alongside normal cert chain. Client only accepts cert if it's included in a global transparency log.
Services (e.g., google.com) also then monitor the global transparency logs for their certs.
Transparency logs return complete inclusion proof (i.e., proves google.com certs returned is complete and not missing any).
If service finds a bad cert, maybe one they didn't request, then they can ban the bad CA from the browser/CA trust roots.
existing merkle accumulator can't easily guarantee completeness b/c the certs are appended in chronological order. log auditors then have to download the entire tree to check for bad certs.
new bilinear accumulator and RSA-based accumulator allow for both lookup proof and append-only proof size in log n
caveat: slightly worse append time and bilinear accum has many public params
these more sophisticated accumulators (bilinear or RSA) allow for O(1) disjointness and subset proofs.
perf: append-only proof: 7 KB, lookup proof: 40-120 KB, reduce communication: 10x-100x
perf: 1 append/sec :0
future work: confident we can go from $4 \lambda$ to $2 \lambda$ to $\log n$ tree depth